import java.util.Arrays;
import java.util.Stack;

public class MyStack {
    public int[] elem;
    public int usedSize;
    public static  final int DEFAULT_CAPACITY = 10;
    public MyStack(){
        this.elem = new int[DEFAULT_CAPACITY];
    }

    public void push(int val){
//        判断栈是否满
        if (isFull()){
//            扩容
            this.elem = Arrays.copyOf(elem,elem.length*2);
            elem[usedSize++] = val;
        }

    }
    private boolean isFull(){
        return usedSize == elem.length;
    }

    public int pop(){
        if (isEmpty()){
            throw new EmptyStackException("栈为空....");
        }
//        elem[usedSize] = null;
        int oldVal = elem[usedSize-1];
        usedSize--;
        return oldVal;
    }
    public boolean isEmpty(){
        return usedSize == 0;
    }
    public int peek(){
        if (isEmpty()){
            throw new EmptyStackException("栈为空....");
        }
        int oldVal = elem[usedSize-1];
        return oldVal;
    }

    public int evalRPN(String[] tokens){
        Stack<Integer> stack =new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            String str = tokens[i];
            if (!isOperations(str)){
//                不是运算符  说明是数字
                int val = Integer.valueOf(str);
                stack.push(val);
            }else {
//                 是运算符
                int num2 = stack.pop();
                int num1 = stack.pop();

                switch (str){
                    case "+":
                        stack.push(num1+num2);
                        break;
                    case "-":
                        stack.push(num1-num2);
                        break;
                    case "*":
                        stack.push(num1*num2);
                        break;
                    case "/":
                        stack.push(num1/num2);
                        break;
                }
            }
        }
        return stack.pop();
    }
    private boolean isOperations(String str){
        if (str.equals("+")|| str.equals("-") ||str.equals("*") ||str.equals("/")){
            return true;
        }
        return false;
    }

//    符号匹配，栈空了就匹配完了
//    只要是左括号就入栈
//    遇到右括号看是否匹配
//    只要右括号不匹配，直接返回false
//    字符串没有遍历完成，栈是空的也是不匹配
//    字符串遍历完成，但是栈还是不为空，此时也是不匹配
    public boolean isValid(String s){
        Stack<Character> stack = new Stack<>();
//        1.遍历字符串
        for (int i = 0; i < s.length(); i++) {
//        2.左括号入栈

//        3.右括号匹配
        }
        return true;
    }

//    public boolean isPopOrder(int[] pushA, int[] popA){
//        Stack<Integer> stack = new Stack<>();
//        int j = 0;
//        for (int i = 0; i < pushA.length; i++) {
//            stack.push(pushA[i]);
////            要有边界判断
//            while (!stack.empty() && j < popA.length && stack.peek() == popA[j]){
//                stack.pop();
//                j++;
//            }
//        }
//        return stack.empty();
//    }
    public boolean isPoopOrder(int[] pushA,int[] popA){
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int i = 0; i < pushA.length; i++) {
            stack.push(pushA[i]);
            while(!stack.isEmpty() && j < popA.length && stack.peek() == popA[j]){
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }

//    最小栈
//    普通栈一定要存储数据
//    最小栈，如果是第一次存放数据，直接放，否则，需要和最小栈的栈顶元素去比较，小于等于的时候才能进

}
